FourNums(LeetCode)

文章目录

1. 1. Question:4Sum
2. 2. SourceCode:
   1. 2.1. s1
   2. 2.2. s2

Question:4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that 

a + b + c + d = target? 

Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

SourceCode:

s1

//笔者提交版本；耗时：46ms；
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
           List<List<Integer>> result = new ArrayList<List<Integer>>();
           int len = nums.length;
           
           if(len < 4){ return result;}
           
           Arrays.sort(nums);
           
           if(nums[len-1]*4< target){return result;}
           
           List<List<Integer>> listTmp = null;
           for(int i = 0,iLoc = len-3 ; i< iLoc; i++){
               //if(nums[i] > target && target>=0){break;}
               if(nums[i]*4 > target ){break;}
               
               int targetT = target - nums[i];
               listTmp = threeSum(nums,i+1,len ,targetT );
               
               for(List<Integer> tHV:listTmp){
                   
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[i]);
                    tmp.add(tHV.get(0));
                    tmp.add(tHV.get(1));
                    tmp.add(tHV.get(2));
                    result.add(tmp);
               }
               //debug
               //if(i == 1){System.out.println(result);}
               
               while(i<iLoc-1 && nums[i]==nums[i+1]){
                   //System.out.println(i);
                   i++;
               }
           }
           
           if(null!=listTmp){
               listTmp.clear();
           }
           
           return result;
    }
    
    
    public List<List<Integer>> threeSum(int[] nums,int start,int len, int target ){
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        List<List<Integer>> listTmp = null;
        
        if(nums[len-1]*3< target){return list;}
        
        for(int i = start,iLoc = len -2  ;i< iLoc;i++){
               
               if(nums[i]*3 > target){break;}
              // if(nums[i] > target && target>=0){break;}
               
               int targetT = target - nums[i];
               listTmp = twoSum(nums,i+1,len ,targetT );
               
               for(List<Integer> tV:listTmp){
                   
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[i]);
                    tmp.add(tV.get(0));
                    tmp.add(tV.get(1));
                    list.add(tmp);
               }
               
                //debug1
               //if(i == 3 ){System.out.println(list);}
               
               while(i<iLoc-1 && nums[i]==nums[i+1]){
                   i++;
                  // System.out.println(i);
               }
           }
           if(null!=listTmp){
               listTmp.clear();
           }
           return list;
    }
    
    public List<List<Integer>> twoSum(int[] nums,int start,int len, int target ){
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        
        if(target> nums[len-1]+nums[len-2]){
           return list;
        }
        
        for(int i = start,iLoc = len ;i< iLoc;i++){
            /*int targetT = target - nums[i];
            if(nums[i] > targetT){break;}*/
            
            
            //if(target < nums[i]*2){break;}
            //这个地方还有的疑惑，为啥不可以这样写？
            
            boolean move = false;
            while(i<len-1 && nums[i]==nums[i+1]){
                   i++;
                   move = true;
            }

           // if(target ==-2){System.out.println(target);}

            //System.out.println(target);

            //[0,0,0,0] 
            //0
            //so add target!=nums[i]*2
            if(map.containsKey(nums[i]) || target == nums[i]*2 && move){
                List<Integer> tmp = new ArrayList<Integer>();
                //进来却没有Key，是因为target == nums[i]*2，即还没来得及放进去
                tmp.add(map.get(nums[i])==null ? nums[i]:map.get(nums[i]));
                tmp.add(nums[i]);
                list.add(tmp);
            }      
            
            map.put(target - nums[i],nums[i]);
            
        }
        map.clear();
        return list;
    }
    
}

s2

//该版本参考了Discuss,还没看Discuss；耗时：ms；
//待写